package com.lw.leetcode.hash.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * c
 * map
 * 2561. 重排水果
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/6 11:18
 */
public class MinCost {

    public static void main(String[] args) {
        MinCost test = new MinCost();

        // 1
//        int[] basket1 = {4, 2, 2, 2};
//        int[] basket2 = {1, 4, 1, 2};

        // -1
//        int[] basket1 = {2, 3, 4, 1};
//        int[] basket2 = {3, 2, 5, 1};

        // 48
//        int[] basket1 = {84, 80, 43, 8, 80, 88, 43, 14, 100, 88};
//        int[] basket2 = {32, 32, 42, 68, 68, 100, 42, 84, 14, 8};

        // 48
        int[] basket1 = {80, 43, 80, 88, 43, 88, 8};
        int[] basket2 = {32, 32, 42, 68, 68, 42, 8};

        long l = test.minCost(basket1, basket2);
        System.out.println(l);
    }

    public long minCost(int[] basket1, int[] basket2) {
        Map<Integer, Integer> ms1 = new HashMap<>();
        Map<Integer, Integer> ms2 = new HashMap<>();
        for (int i : basket1) {
            ms1.merge(i, 1, (a, b) -> a + b);
        }
        for (int i : basket2) {
            ms2.merge(i, 1, (a, b) -> a + b);
        }
        Set<Integer> set = new HashSet<>();
        set.addAll(ms1.keySet());
        set.addAll(ms2.keySet());
        int length = set.size();
        int[] arr = new int[length];
        int[] counts = new int[length];
        int index = 0;
        int s = 0;
        for (Integer v : set) {
            arr[index++] = v;
        }
        Arrays.sort(arr);
        for (int i = 0; i < length; i++) {
            int v = arr[i];
            int c1 = ms1.getOrDefault(v, 0);
            int c2 = ms2.getOrDefault(v, 0);
            if (((c1 + c2) & 1) == 1) {
                return -1;
            }
            counts[i] = Math.abs(c1 - c2);
            s += Math.abs(c1 - c2);
        }
        int m = arr[0];
        int t = arr[0] << 1;
        s -= (counts[0] << 1);
        long value = (counts[0] >> 1) * (long) m;
        for (int i = 1; i < length; i++) {
            if (s == 0) {
                break;
            }
            int c = counts[i];
            if (c == 0) {
                continue;
            }
            int v = arr[i];
            if (s < (c << 1)) {
                c = s >> 1;
            }
            s -= (c << 1);
            if (v > t) {
                value += (c * m);
            } else {
                value += ((c * v) >> 1);
            }
        }
        return value;
    }

}
